/*
 * postfix expression such as “abc*+de*f+g*+” to tree.
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct stack{
    void * block[100];
    int p;
};

void push(struct stack * stk, void * item){
    stk->block[(stk->p)++] = item;
}

void * pop(struct stack * stk){
    return stk->block[--(stk->p)];
}

int is_empty(struct stack * stk){
    return (stk->p == 0);
}

void init(struct stack * stk){
    stk->p = 0;
}

struct node{
    char name;
    struct node * lchild;
    struct node * rchild;
};

int is_op(char chr){
    return  chr == '+' ||
            chr == '-' ||
            chr == '*' ||
            chr == '/'
            ;
}
struct node *  postfix_to_tree(char * expr){
    int i;
    int len = strlen(expr);
    struct stack node_stk;
    init(&node_stk);
    struct node * cur_node;
    for (i=0; i<len; i++){
        cur_node = (struct node * ) malloc(sizeof(struct node));
        cur_node ->name = expr[i];
        cur_node ->lchild = NULL;
        cur_node ->rchild = NULL;
        if (is_op(expr[i])){
            cur_node->lchild = pop(&node_stk);
            cur_node->rchild = pop(&node_stk);
            push(&node_stk, cur_node);
        }else{
            push(&node_stk, cur_node);
        }
    }
    return cur_node;
}

int main() {
    char expr[] =  "abc*+de*f+g*+";
    struct node * result  =  postfix_to_tree(expr);
    printf("Hello, World!\n");
    return 0;
}
